package com.xie.leetcode.tree;

//1609. 奇偶树
//        如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
//
//        二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
//        偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
//        奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
//        给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
//
//
//
//        示例 1：
//
//
//
//        输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
//        输出：true
//        解释：每一层的节点值分别是：
//        0 层：[1]
//        1 层：[10,4]
//        2 层：[3,7,9]
//        3 层：[12,8,6,2]
//        由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。
//        示例 2：
//
//
//
//        输入：root = [5,4,2,3,3,7]
//        输出：false
//        解释：每一层的节点值分别是：
//        0 层：[5]
//        1 层：[4,2]
//        2 层：[3,3,7]
//        2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
//        示例 3：
//
//
//
//        输入：root = [5,9,1,3,5,7]
//        输出：false
//        解释：1 层上的节点值应为偶数。
//        示例 4：
//
//        输入：root = [1]
//        输出：true
//        示例 5：
//
//        输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
//        输出：true
//
//
//        提示：
//
//        树中节点数在范围 [1, 105] 内
//        1 <= Node.val <= 10^6

import com.xie.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiezhendong
 * @date 2021/12/25
 */
public class IsEvenOddTree {

    public static void main(String[] args) {
        IsEvenOddTree isEvenOddTree = new IsEvenOddTree();

        TreeNode root123Left = new TreeNode(12);
        TreeNode root123Right = new TreeNode(8);

        TreeNode root12Left = new TreeNode(3, root123Left, root123Right);

        TreeNode root223Left = new TreeNode(6);

        TreeNode root22Left = new TreeNode(7, root223Left, null);

        TreeNode root223Right = new TreeNode(2);

        TreeNode root22Right = new TreeNode(9, null, root223Right);

        TreeNode root1Left = new TreeNode(10, root12Left, null);
        TreeNode root1Right = new TreeNode(4, root22Left, root22Right);
        TreeNode root0 = new TreeNode(1, root1Left, root1Right);
        System.out.println(isEvenOddTree.isEvenOddTree(root0));
    }

    public boolean isEvenOddTree(TreeNode root) {
        List<TreeNode> valList = new ArrayList<>();

        int rowNum = 0;

        valList.add(root);
        if (root.val % 2 == 0){
            return  false;
        }

        while (valList.size() > 0) {
            List<TreeNode> valNextList = new ArrayList<>();

            System.out.print(rowNum + "层:");
            rowNum++;

            for (TreeNode treeNode : valList) {
                System.out.print(treeNode.val);
                System.out.print("  ");

                if (treeNode.left != null) {
                    valNextList.add(treeNode.left);
                }
                if (isCheck(rowNum, valNextList)) {
                    return false;
                }
                if (treeNode.right != null) {
                    valNextList.add(treeNode.right);
                }
                if (isCheck(rowNum, valNextList)) {
                    return false;
                }
            }

            System.out.println();

            valList = new ArrayList<>(valNextList);

        }
        return true;
    }

    private boolean isCheck(int rowNum, List<TreeNode> valList) {
        if (valList.size() == 0) {
            return false;
        }
        if (rowNum % 2 == 0) {
            // 偶数
            int val = valList.get(valList.size() - 1).val;
            if (val % 2 == 0) {
                return true;
            }
            if (valList.size() >= 2) {
                int valLast = valList.get(valList.size() - 2).val;
                if (valLast >= val) {
                    return true;
                }
            }
        } else {
            // 奇数
            int val = valList.get(valList.size() - 1).val;
            if (val % 2 == 1) {
                return true;
            }
            if (valList.size() >= 2) {
                int valLast = valList.get(valList.size() - 2).val;
                if (valLast <= val) {
                    return true;
                }
            }
        }
        return false;
    }
}
